package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/"> 从上到下打印二叉树 I</a>
 * <p>从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。</p>
 * <pre>
 *          3
 *         /  \
 *        9    20
 *            /  \
 *           15    7
 *  输入：{3,9,20,null,null,15,7}
 *  返回值：[3,9,20,15,7]
 * </pre>
 *
 * @author c2b
 * @since 2023/3/9 13:44
 */
public class JzOffer0032LevelOrder_I {
    /**
     * <p>队列</p>
     * step 1：首先判断二叉树是否为空，空树没有遍历结果。<br>
     * step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。<br>
     * step 3：每次遍历队首节点，如果它们有子节点，依次(先左后右)加入队列排队等待访问。<br>
     */
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> resList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode currentNode;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            resList.add(currentNode.val);
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }
        int[] res = new int[resList.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = resList.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(1);
        JzOffer0032LevelOrder_I jzOffer0032LevelOrder_i = new JzOffer0032LevelOrder_I();
        int[] ints = jzOffer0032LevelOrder_i.levelOrder(root);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
